home *** CD-ROM | disk | FTP | other *** search
/ Power Programmierung / Power-Programmierung (Tewi)(1994).iso / magazine / drdobbs / 1991 / 02 / cprog.asc < prev    next >
Text File  |  1990-12-26  |  6KB  |  251 lines
  1. _C PROGRAMMING COLUMN_
  2. by Al Stevens
  3.  
  4.  
  5. [LISTING ONE]
  6.  
  7. /* ------------------- htree.h -------------------- */
  8. typedef unsigned int BYTECOUNTER;
  9.  
  10. /* ---- Huffman tree structure ---- */
  11. struct htree    {
  12.     unsigned char ch;       /* character value             */
  13.     BYTECOUNTER cnt;        /* character frequency         */
  14.     struct htree *parent;   /* pointer to parent node      */
  15.     struct htree *right;    /* pointer to right child node */
  16.     struct htree *left;     /* pointer to left child node  */
  17. };
  18. extern struct htree ht[];
  19. extern struct htree *root;
  20.  
  21. void buildtree(void);
  22.  
  23.  
  24.  
  25. [LISTING TWO]
  26.  
  27. /* ------------------- htree.c -------------------- */
  28. #include <stdio.h>
  29. #include <stdlib.h>
  30. #include "htree.h"
  31.  
  32. struct htree ht[512];
  33. struct htree *root;
  34.  
  35. /* ------ build a Huffman tree from a frequency array ------ */
  36. void buildtree(void)
  37. {
  38.     int treect = 256;
  39.     int i;
  40.  
  41.     /* ---- build the huffman tree ----- */
  42.     while (1)   {
  43.         struct htree *h1 = NULL, *h2 = NULL;
  44.         /* ---- find the two smallest frequencies ---- */
  45.         for (i = 0; i < treect; i++)   {
  46.             if (ht+i != h1) {
  47.                 if (ht[i].cnt > 0 && ht[i].parent == NULL)   {
  48.                     if (h1 == NULL || ht[i].cnt < h1->cnt) {
  49.                         if (h2 == NULL || h1->cnt < h2->cnt)
  50.                             h2 = h1;
  51.                         h1 = ht+i;
  52.                     }
  53.                     else if (h2 == NULL || ht[i].cnt < h2->cnt)
  54.                         h2 = ht+i;
  55.                 }
  56.             }
  57.         }
  58.         if (h2 == NULL) {
  59.             root = h1;
  60.             break;
  61.         }
  62.         /* --- combine two nodes and add one --- */
  63.         h1->parent = ht+treect;
  64.         h2->parent = ht+treect;
  65.         ht[treect].cnt = h1->cnt + h2->cnt;
  66.         ht[treect].right = h1;
  67.         ht[treect].left = h2;
  68.         treect++;
  69.     }
  70. }
  71.  
  72.  
  73.  
  74. [LISTING THREE]
  75.  
  76. /* ------------------- huffc.c -------------------- */
  77. #include <stdio.h>
  78. #include <stdlib.h>
  79. #include "htree.h"
  80.  
  81. static void compress(FILE *fo, struct htree *h,struct htree *child);
  82. static void outbit(FILE *fo, int bit);
  83.  
  84. void main(int argc, char *argv[])
  85. {
  86.     FILE *fi, *fo;
  87.     int c;
  88.     BYTECOUNTER bytectr = 0;
  89.     int freqctr = 0;
  90.     if (argc < 3)   {
  91.         printf("\nusage: huffc infile outfile");
  92.         exit(1);
  93.     }
  94.  
  95.     if ((fi = fopen(argv[1], "rb")) == NULL)    {
  96.         printf("\nCannot open %s", argv[1]);
  97.         exit(1);
  98.     }
  99.     if ((fo = fopen(argv[2], "wb")) == NULL)    {
  100.         printf("\nCannot open %s", argv[2]);
  101.         fclose(fi);
  102.         exit(1);
  103.     }
  104.  
  105.     /* - read the input file and count character frequency - */
  106.     while ((c = fgetc(fi)) != EOF)   {
  107.         c &= 255;
  108.         if (ht[c].cnt == 0)   {
  109.             freqctr++;
  110.             ht[c].ch = c;
  111.         }
  112.         ht[c].cnt++;
  113.         bytectr++;
  114.     }
  115.  
  116.     /* --- write the byte count to the output file --- */
  117.     fwrite(&bytectr, sizeof bytectr, 1, fo);
  118.  
  119.     /* --- write the frequency count to the output file --- */
  120.     fwrite(&freqctr, sizeof freqctr, 1, fo);
  121.  
  122.     /* -- write the frequency array to the output file -- */
  123.     for (c = 0; c < 256; c++)   {
  124.         if (ht[c].cnt > 0)    {
  125.             fwrite(&ht[c].ch, sizeof(char), 1, fo);
  126.             fwrite(&ht[c].cnt, sizeof(BYTECOUNTER), 1, fo);
  127.         }
  128.     }
  129.  
  130.     /* ---- build the huffman tree ---- */
  131.     buildtree();
  132.  
  133.     /* ------ compress the file ------ */
  134.     fseek(fi, 0L, 0);
  135.     while ((c = fgetc(fi)) != EOF)
  136.         compress(fo, ht + (c & 255), NULL);
  137.     outbit(fo, -1);
  138.     fclose(fi);
  139.     fclose(fo);
  140. }
  141.  
  142. /* ---- compress a character value into a bit stream ---- */
  143. static void compress(FILE *fo, struct htree *h,
  144.                                 struct htree *child)
  145. {
  146.     if (h->parent != NULL)
  147.         compress(fo, h->parent, h);
  148.     if (child)  {
  149.         if (child == h->right)
  150.             outbit(fo, 0);
  151.         else if (child == h->left)
  152.             outbit(fo, 1);
  153.     }
  154. }
  155. static char out8;
  156. static int ct8;
  157.  
  158. /* -- collect and write bits to the compressed output file -- */
  159. static void outbit(FILE *fo, int bit)
  160. {
  161.     if (ct8 == 8 || bit == -1)  {
  162.         fputc(out8, fo);
  163.         ct8 = 0;
  164.     }
  165.     out8 = (out8 << 1) | bit;
  166.     ct8++;
  167. }
  168.  
  169.  
  170.  
  171. [LISTING FOUR]
  172.  
  173. /* ------------------- huffd.c -------------------- */
  174. #include <stdio.h>
  175. #include <stdlib.h>
  176. #include "htree.h"
  177.  
  178. static int decompress(FILE *fi, struct htree *root);
  179.  
  180. void main(int argc, char *argv[])
  181. {
  182.     FILE *fi, *fo;
  183.     unsigned char c;
  184.     BYTECOUNTER bytectr;
  185.     int freqctr;
  186.     if (argc < 3)   {
  187.         printf("\nusage: huffd infile outfile");
  188.         exit(1);
  189.     }
  190.     if ((fi = fopen(argv[1], "rb")) == NULL)    {
  191.         printf("\nCannot open %s", argv[1]);
  192.         exit(1);
  193.     }
  194.     if ((fo = fopen(argv[2], "wb")) == NULL)    {
  195.         printf("\nCannot open %s", argv[2]);
  196.         fclose(fi);
  197.         exit(1);
  198.     }
  199.  
  200.     /* ----- read the byte count ------ */
  201.     fread(&bytectr, sizeof bytectr, 1, fi);
  202.  
  203.     /* ----- read the frequency count ------ */
  204.     fread(&freqctr, sizeof freqctr, 1, fi);
  205.  
  206.     while (freqctr--)   {
  207.         fread(&c, sizeof(char), 1, fi);
  208.         ht[c].ch = c;
  209.         fread(&ht[c].cnt, sizeof(BYTECOUNTER), 1, fi);
  210.     }
  211.  
  212.     /* ---- build the huffman tree ----- */
  213.     buildtree();
  214.  
  215.     /* ----- decompress the file ------ */
  216.     while (bytectr--)
  217.         fputc(decompress(fi, root), fo);
  218.     fclose(fo);
  219.     fclose(fi);
  220. }
  221. static int in8;
  222. static int ct8 = 8;
  223.  
  224. /* ---- read a bit at a time from a file ---- */
  225. static int inbit(FILE *fi)
  226. {
  227.     int obit;
  228.     if (ct8 == 8)   {
  229.         in8 = fgetc(fi);
  230.         ct8 = 0;
  231.     }
  232.     obit = in8 & 0x80;
  233.     in8 <<= 1;
  234.     ct8++;
  235.     return obit;
  236. }
  237.  
  238. /* ----- decompress file bits into characters ------ */
  239. static int decompress(FILE *fi, struct htree *h)
  240. {
  241.     while (h->right != NULL)
  242.         if (inbit(fi))
  243.             h = h->left;
  244.         else
  245.             h = h->right;
  246.     return h->ch;
  247. }
  248.  
  249.  
  250.  
  251.